Задача о ранце


Задача о ранце

Задача о ранце (или «о рюкзаке«) [problem of knapsack] — задача о наилучшем выборе предметов из общего их количества таким образом, чтобы их суммарный вес (или габариты и т.п.) не превышал заданного, а их суммарная полезность, или иная общая оценка, была максимальной. Решается как задача целочисленного линейного программирования, методами динамического программирования и др. Применяется, например, при планировании оптимальной загрузки самолетов, кораблей, складов.

  • · Упрощенно модель задачи о ранце можно записать так:

Найти

т.е. наибольшую ценность груза (xi — количество, viстоимость предмета i-го вида, i = 1, 2, …, n);

при условиях:

т.е. вес груза не превышает грузоподъемности ранца W (pi — вес i-го предмета);

xi = 0, 1, 2,..

Последнее условие говорит о том, что предметы неделимы (условие целочисленности).


Экономико-математический словарь: Словарь современной экономической науки. — М.: Дело. . 2003.

Смотреть что такое "Задача о ранце" в других словарях:

  • задача о ранце — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] задача о ранце задача о рюкзаке Задача о наилучшем выборе предметов из общего их количества таким образом, чтобы их суммарный вес (или габариты и т.п.) не превышал заданного, а …   Справочник технического переводчика

  • Задача о ранце — Пример задачи о ранце: необходимо разместить ящики в рюкзак при условии на вместимость рюкзака 15 кг, так чтобы суммарная полезность предметов в рюкзаке была максимальной. Задача о ранце (рюкзаке) (англ.  …   Википедия

  • ЗАДАЧА О РАНЦЕ — задача целочисленного программирования: имеется ранец объема V и неограниченное количество из N различных предметов. Для каждого предмета i го типа при i = 1, 2, ..., N известны его объем V и ценности mi. В ранец можно положить целое число… …   Большой экономический словарь

  • ЗАДАЧА О РАНЦЕ — (KNAPSACK PROBLEM) задача программирования целочисленного: имеется ранец объема V и неограниченное кол во каждого из Л различных предметов. Для каждого предмета 1 го типа при ( 1,2,..., N известны его объем Vi и ценность т/. В ранец можно… …   Глоссарий терминов по грузоперевозкам, логистике, таможенному оформлению

  • Задача о ранце в криптографии — (англ. Knapsack problem)  это задача, на основе которой американские криптографы Ральф Меркл (англ.) и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом. Он носит название криптосистема Меркла Хеллмана. Для… …   Википедия

  • Задача о рюкзаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… …   Википедия

  • Задача о рюказаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… …   Википедия

  • Задача SAT — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Задача ВЫП — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Задача о вершинном покрытии — NP полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP полноты более сложных задач. Содержание 1 Определение 2 NP полнота 3 Ссылки …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.